/*--- cksmtest.c -------------------------- Listing 10-3 -------
 *  Test checksum methods to see the distribution of checksums
 *  when transpositions occur. Performs the testing on 100
 *  random 10-digit numbers all the way to 100 2-digit
 *  numbers. Benign transpositions (see text) are not included.
 *-------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

char table [100] [10]; /* the table of random digits */
                       /* max: 10 numbers of 10 digits each */

void DisplayUsage ( void );
void LoadTableRandom ( char * );
int  GetChecksum ( char *, int, int );

int main( int argc, char *argv[] )
{
    int  i, j, size, method;
    char *p, *pmax;
    char buffer[10];

    p = (char *) table;     /* start of table */
    pmax = p + 1000;        /* end of table */

    if ( argc != 2 )
    {
        DisplayUsage();
        return ( EXIT_FAILURE );
    }
    else
        method = atoi ( argv[1] );

    switch ( method )
    {
        case 1: printf ( "Using 7 mod 11\n\n" );    break;
        case 2: printf ( "Using 9 mod 11\n\n" );    break;
        case 3: printf ( "Using 7 mod 26\n\n" );    break;
        case 4: printf ( "Using 7 mod 10\n\n" );    break;
        case 5: printf ( "Using 9 mod 10\n\n" );    break;
        default:
                DisplayUsage();
                return ( EXIT_FAILURE );
    }

    /* we loop through for every size from 10 to 2.
     * We don't handle 1-digit numbers since they
     * offer no possibility of transpositions.
     */

    for ( size = 10; size > 1; size-- )
    {
        int collisions = 0;

        /* Load the table with random digits */

        LoadTableRandom ( pmax );

        /* main test loop: we process 100 numbers
         * of length size. For each number, we do every
         * possible transposition and get its checksum.
         */

        for ( i = 0, p = (char *)table; i < 100;
                                           i++, p += size )
        {
            int k, l, orig_cksum;

            /* get the original number's checksum */

            orig_cksum = GetChecksum ( p, size, method );

            /* now copy the number to buffer, where we'll
             * do the transpositions.
             */

            memcpy ( buffer, p, size );

            /* do the transpositions and checksums */

            for ( k = 0; k < size - 1; k++ )
            {
                /* is there a transposition possible?
                 * if both digits are the same, they cannot
                 * be transposed; so skip these, otherwise
                 * they will generate bogus collisions.
                 */

                if ( buffer[k] == buffer[k + 1] )
                    continue;

                /* otherwise, do the transposition */

                l = buffer[k + 1];
                buffer[k + 1] = buffer[k];
                buffer[k] = (char) l;

                /* get the checksum */

                j = GetChecksum ( buffer, size, method );

                if ( j == orig_cksum )
                    collisions += 1;

                /* now undo this transposition */

                l = buffer[k + 1];
                buffer[k + 1] = buffer[k];
                buffer[k] = (char) l;
            }

        }   /* end of loop processing numbers of one size */

        printf ( "%2d digits avg. %1.2f collisions\n",
                    size, (float) ( collisions / 100.0 ));

        collisions = 0;
    }

    return ( EXIT_SUCCESS );
}

void LoadTableRandom ( char *table_end )
{
    int i;
    unsigned short int j;
    char *p, *p2;

    /* 200 random ints will get us close to 1000 digits
     * we presume it gets us at least 500 digits, which is
     * a safe bet, but will not always be the case.
     */

    p = (char *) table;

    for ( i = 0; i < 200; i++ )
    {
        j = (short int) rand();
        sprintf ( p, "%u", j );
        p += strlen ( p );
    }

    /* how many digits left to fill out? */

    i = table_end - p;

    p2 = p - 1;

    /* go backwards from p and copy digits into the
     * remaining table space. This will copy i digits
     * prior to p and place them in reverse order after p.
     */
    while ( i )
    {
        *p++ = *p2--;
        i--;
    }
}

int GetChecksum ( char *data, int length, int which_test )
{
    int  i, j;
    int  position;
    unsigned long int sum;
    long int *powers;

    static long int powers_of_7 [10] = { 1, 7, 49, 343, 2401,
            16807, 117649, 823543, 5764801, 40353607 };

    static long int powers_of_9 [10] = { 1, 9, 81, 729, 6561,
            59049, 531441, 4782969, 43046721, 387420489 };

    if ( which_test == 2 || which_test == 5 )
        powers = powers_of_9;
    else
        powers = powers_of_7;

    /* make sure all digits can be looked up */

    if ( length > 10 )
        return ( -1 );

    sum = 0L;
    position = 0; /* what digit in the data are we at? */

    for ( i = length; i > 0; i--, position++ )
    {
        /* do we have a digit ? */

        if ( ! isdigit ( data[i-1] ))
            return ( -2 );

        /* convert digit character to a number */

        j = data[i-1] - '0';

        /* look up power, multiply by j, add to sum */

        sum += powers [position] * j;
    }

    /* get the sum modulus depending on method */

    switch ( which_test )
    {
        case 1:
        case 2:
            i = (int) ( sum % 11L );
            if ( i == 10 )
                i = 0;
            break;
        case 3:
            i = (int) ( sum % 26L );    break;
        case 4:
        case 5:
            i = (int) ( sum % 10L );    break;
        default:
            DisplayUsage();
            exit ( EXIT_FAILURE );
    }

    return ( i );
}

void DisplayUsage()
{
    fprintf ( stderr,
        "Error: need to specify checksum method to test\n"
        "1. Powers of 7 Mod 11\n"
        "2. Powers of 9 Mod 11\n"
        "3. Powers of 7 Mod 26\n"
        "4. Powers of 7 Mod 10\n"
        "5. Powers of 9 Mod 10\n" );
}
